{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 什么是数据结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 数据结构的定义"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**数据结构是指数据以及相互之间的联系。**\n",
    "\n",
    "1. 数据之间的逻辑关系，即数据的逻辑结构。\n",
    "> 数据的逻辑结构是从逻辑关系（主要是指相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。可以看作是从具体问题抽象出来的数学模型。\n",
    "\n",
    "2. 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也成为数据的物理结构。\n",
    "> 数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示，也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。一般只在高级语言的层次上来讨论存储结构。\n",
    "\n",
    "3. 施加在该数据上的操作，即数据的运算。\n",
    "> 数据的运算是定义在数据的逻辑结构之上的，每种逻辑结构都有一组相应的运算。例如检索、插入、删除、更新、排序等，数据的运算最终需要在对应的存储结构上用算法实现。\n",
    "\n",
    "因此，数据结构是用来 **描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 逻辑结构类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. 集合**\n",
    "\n",
    "数据元素之间出了同属于一个集合的关系外，没有其他关系。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. 线性结构**\n",
    "\n",
    "结点存在一对一的关系。开始结点和终端结点是唯一的，出了开始结点和终端结点之外，其余结点都有且仅有一个直接前驱，有且仅有一个直接后继。顺序表就是一种典型的线性结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. 树形结构**\n",
    "\n",
    "结点之间存在一对多的关系。每个结点最多只有一个直接前驱，但可以有多个直接后继，可以有多个终端结点。二叉树就是一种典型的树形结构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4. 图形结构**\n",
    "\n",
    "结点之间存在多对多的关系。每个结点的直接前驱和直接后继的个数都是任意的。因此图形结构可能没有开始结点和终端结点，也可能有多个开始结点和终端结点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 树形结构和图形结构统称为非线性结构，该结构重的结点之间存在一对多或多对多的关系。线性结构是树形结构的特殊情况，树形结构是图形结构的特殊情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 存储结构类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. 顺序存储结构**\n",
    "\n",
    "把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于计算机程序设计语言的数组来描述的。\n",
    "\n",
    "- 优点\n",
    "\n",
    "节省存储空间，结点之间的逻辑关系没有占用额外的存储空间。\n",
    "\n",
    "可实现对结点的随机存取。\n",
    "\n",
    "- 缺点\n",
    "\n",
    "不便于修改，对结点的插入、删除运算，需要移动一系列的结点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. 链式存储结构**\n",
    "\n",
    "不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是通过附加的指针字段表示的。通常要借助于计算机程序设计语言的指针类型来描述。\n",
    "\n",
    "- 优点\n",
    "\n",
    "便于修改，插入、删除运算仅需修改相应结点的指针域，不必移动结点。\n",
    "\n",
    "- 缺点\n",
    "\n",
    "存储空间的利用率较低，存储单元有一部分被用来存储结点之间的逻辑关系了。\n",
    "\n",
    "逻辑相邻的结点在存储空间中不一定相邻，不能对结点进行随机存取。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. 索引存储结构**\n",
    "\n",
    "通常在存储结点信息的同时还建立附加的索引表。索引表中的每一项成为索引项，索引项的一般形式是：（关键字，地址），关键字唯一标识一个结点，地址作为指向结点的指针。\n",
    "\n",
    "- 优点\n",
    "\n",
    "可以对结点进行随机访问。\n",
    "\n",
    "插入、删除时，只需移动存储在索引表中对应结点的存储地址，不必移动存放在结点表中结点的数据，所以仍保持较高的数据修改运算效率。\n",
    "\n",
    "- 缺点\n",
    "\n",
    "增加了索引表，降低了存储空间的利用率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4. 哈希(或散列)存储结构**\n",
    "\n",
    "基本思想是根据结点的关键字通过哈希函数直接计算出一个值，并将这个值作为该结点的存储地址。\n",
    "\n",
    "- 优点\n",
    "\n",
    "查找速度快，只要给出待查结点的关键字，就可以立即计算出该结点的存储地址。\n",
    "\n",
    "- 缺点\n",
    "\n",
    "只能存储结点的数据，不存储结点之间的逻辑关系。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. 数据结构和数据类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. 数据类型\n",
    "对应计算机语言中的类型，如基本数据类型（int，float）、指针类型、数组类型、结构体类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 抽象数据类型\n",
    "从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，对应计算机语言中的类"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
